The SM2 digital signature algorithm which is a component of the Public Key Cryptographic Algorithm SM2 Based on Elliptic Curves has been well applied in the field of user identity authentication and information integrity check functions. The operational efficiency of the SM2 digital signature algorithm has been the focus of attention by the users of the algorithm being applied. The SM2 digital signature algorithm is consisted of the SM2 digital signature generation algorithm and the SM2 digital signature verification algorithm.
If M represents a message to be signed, then in order to obtain a digital signature (r, s) of the message M, to be used by a user A, this can be performed in the following SM2 digital signature generation algorithm:
A1: Set M=ZA∥M.
Where ∥ represents a cascading operation, and ZA represents a hash value of the user A, obtained in a cryptographic hash function, to generate the digital signature.
A2: Calculate e=Hν(M), and convert the data type of e from a string of bits into an integer.
Where Hν( ) represents a cryptographic hash function with a message digest length of ν bits, e.g., the SM3 Cryptographic Hash Algorithm.
A3: Generate a random number k∈[1, n−1] using a random number generator.
Where n represents a parameter of an elliptical curve.
A4: Calculate a point (x1,y1)=[k]G on the elliptical curve, where x1 represents a field element, and convert the data type of x1 into an integer.
Where G represents a basic point on the elliptical curve, and [k]G represents the point multiplication of k and G.
The type of an equation of the elliptical curve can be a prime number field equation y2=x3+ax+b or a binary field equation y2+xy=x3+ax2+b.
A5: Calculater=(e+x1)mod n  Equation 1
That is, a modular operation is performed on n using (e+x1).
If r=0 or r+k=n, then A3 is returned.
A6: Calculates=((1+dA)−1·(k−r·dA))mod n  Equation 2
If s=0, then A3 is returned.
Where dA represents a private key of the user A.
A7: Convert the data type of r and s from an integer into a string of bytes, and the digital signature of the message M is (r, s).
The user A can be a system or a device, and the SM2 digital signature generation algorithm can be performed by a subsystem or a hardware module arranged in the user A, a software module executable in the user A, etc., or can be a system or a device, in communication with the user A, invoked by the user A.
The user A is provided with a distinguishable identity IDA with the length of entlenA bits, where ENTLA represents two bytes into which an integer entlenA is converted. In the SM2 digital signature generation algorithm, the data type of the coordinates xG and yG of G, and the coordinates xA and yA of PA are converted into a string of bits, so ZA=H256(ENTLA∥IDA∥a∥b∥xG∥yG∥xA∥yA), where PA represents a public key of the user A, and H256( ) represents a cryptographic hash function with a message digest length of 256 bits, e.g., the SM3 Cryptographic Hash Algorithm.
Moreover in a particular engineering implementation, those skilled in the art typically transform Equation 2 as in Equation 3 and Equation 4 below by converting a negative integral power algorithm, i.e., (1+dA)−1, into performing a modular inverse algorithm, i.e., (1+dA)−1 mod n, to thereby facilitate the engineering implementation.s=(((1+dA)−1 mod n)·((k−r−dA)mod n))mod n  Equation 3s=(((1+dA)−1 mod n)·((k−(r−dA)mod n)mod n))mod n  Equation 4
The SM2 digital signature generation algorithm is performed based upon the theory of the ECC algorithm where large integer multiplication, large integer modular multiplication, and other large integer operations are the most significant factor to influence the operational efficiency of the algorithm, and although the existing SM2 digital signature generation algorithm can satisfy some demand for the operational efficiency, it may be desirable to further improve the operational efficiency, and there has been absent a corresponding solution in the prior art.